package main

import (
	"fmt"
	"math"
)

func main() {
	fmt.Printf("minCostTickets([]int{1, 4, 6, 7, 8, 20}, []int{2, 7, 15}): %v\n",
		mincostTickets([]int{1, 4, 6, 7, 8, 20}, []int{2, 7, 15}))
}

/*
*
在一个火车旅行很受欢迎的国度，
你提前一年计划了一些火车旅行。
在接下来的一年里，你要旅行的日子将以一个名为 days 的数组给出。
每一项是一个从 1 到 365 的整数。
火车票有 三种不同的销售方式 ：

一张 为期一天 的通行证售价为 costs[0] 美元；
一张 为期七天 的通行证售价为 costs[1] 美元；
一张 为期三十天 的通行证售价为 costs[2] 美元。
通行证允许数天无限制的旅行。 例如，如果我们在第 2 天获得一张 为期 7 天 的通行证，那么我们可以连着旅行 7 天：第 2 天、第 3 天、第 4 天、第 5 天、第 6 天、第 7 天和第 8 天。

返回 你想要完成在给定的列表 days 中列出的每一天的旅行所需要的最低消费 。
*/
func mincostTickets(days []int, costs []int) int {
	dp := make([]int, len(days))
	return f(days, costs, 0, dp)
}

var choices = []int{1, 7, 30}

func f(days []int, costs []int, start int, dp []int) int {
	// 超过了最后一天，直接返回0
	if start == len(days) {
		return 0
	}
	// dp[start], 下标i这一天已经算过了，直接返回
	if dp[start] != 0 {
		return dp[start]
	}
	// 默认最大值
	cost := math.MaxInt
	// 三种方案。1天、7天、30天
	for choice, j := 0, start; choice < 3; choice++ {
		// 每种方案都去找可以最多包含到哪一天
		for j < len(days) && days[start]+choices[choice] > days[j] {
			j++
		}
		// 尝试去寻找最小值
		// 当前天的choice方案的花费+票过期的那天的花费的最小值
		cost = min(cost, costs[choice]+f(days, costs, j, dp))
	}
	dp[start] = cost
	return cost
}

// 从递归到动态规划， 找转移方程，其实就是递归中的尝试
func f2(days []int, costs []int) int {
	n := len(days)
	dp := make([]int, n+1)
	for i := 0; i < n+1; i++ {
		dp[i] = math.MaxInt
	}
	dp[n] = 0
	for i := n - 1; i >= 0; i-- {
		// 三种方案。1天、7天、30天
		for choice, j := 0, i; choice < 3; choice++ {
			// 每种方案都去找可以最多包含到哪一天
			for j < len(days) && days[i]+choices[choice] > days[j] {
				j++
			}
			// 当前天的choice方案的花费+票过期的那天的花费的最小值
			dp[i] = min(dp[i], costs[choice]+dp[j])
		}
	}
	return dp[0]
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}
